BZOJ1026【SCOI2009】Windy数 <数位DP>

Problem

【SCOI2009】windy数

Description

定义了一种数。不含前导零且相邻两个数字之差至少为的正整数被称为数。想知道，在和之间，包括和，总共有多少个数？

Input

包含两个整数，。

Output

一个整数

Sample Input

输入样例一

1 10

输入样例二

25 50

Sample Output

输出样例一

输出样例二

HINT

数据规模和约定
的数据，满足。

标签：数位DP

Solution

非常经典的一道数位题。
也是多少数位入门的第一题啊…

先预处理出数组，其中从左往右第位为的数的个数。
对于询问，分别计算和中的数的个数，即在预处理的表中按位查询，统计答案后相减即可。

Code

#include <iostream>
#include <cstdio>
using namespace std;
int f[15][15];
int abs(int x) {return x >= 0 ? x : -x;}
int calc(int x) {
    int len = 0, n[15], t = x, ret = 0;	while (t)	n[++len] = t%10, t /= 10;
    for (int i = 1; i < len; i++)	for (int j = 1; j <= 9; j++)	ret += f[i][j];
    for (int i = len; i; i--) {
        for (int j = (i == len ? 1 : 0); j < n[i]; j++)	if (i == len || abs(j-n[i+1]) >= 2)	ret += f[i][j];
        if (i < len && abs(n[i+1]-n[i]) < 2)	break;
    }
    return ret;
}
int main() {
    for (int i = 0; i <= 9; i++)	f[1][i] = 1;
    for (int i = 1; i <= 10; i++)	for (int j = 0; j <= 9; j++) {
        for (int k = 0; k <= j-2; k++)	f[i+1][k] += f[i][j];
        for (int k = j+2; k <= 9; k++)	f[i+1][k] += f[i][j];
    }
    int l, r;	scanf("%d%d", &l, &r);	printf("%d", calc(r+1)-calc(l));
    return 0;
}